package PersonStu.sanqi;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author by KoVaVo
 * @Date 2023-01-03 21:29
 * @Desc:
 * 1、给定一个数组arr,如果有某个数出现次数超过数组长度的一半，打印这个数字，如果没有则不打印。
 * 2、给定一个数组arr和一个整数k，arr的长度为N，如果有某些数超过了N/K,打印这些数字，没有不打印。
 */
public class code_26_FindKMajority {

    public static int method1(int [] arr){
        //遍历数组，
        if(arr == null || arr.length == 0){
            return 0;
        }
        //候选数
        int cand = 0;
        //血量,每次遍历数组的时候，判断下一个数字是否和当前的数字相等
        //1、如果不相等那么HP--
        //1、如果相等那么HP++
        int HP = 0;
        for (int i = 0; i < arr.length; i++) {
            //判断当前的血量是否为0
            if(HP == 0){
                //说明当前的候选数是没有定义数字的
                cand = arr[i];
                HP++;
            }else if(cand == arr[i]){
                HP++;
            } else{
                HP--;
            }
        }
        if(HP == 0){
            System.out.println("没有");
            return 0;
        }
        //拿到了最后一个保留的cand，判断cand的数字，在arr中是否超过它的长度的一半
        for (int i = 0; i < arr.length; i++) {
            if(cand == arr[i]){
                HP++;
            }
        }
        if(HP > arr.length/2){
            System.out.println("这个值就是："+cand);
            return cand;
        }else   {
            System.out.println("没得这样的数字");
        }
        return 0;
    }

    /**
     * 问题2
     * @param arr
     */
    public static void method2(int [] arr,int K){
        if(K < 2){
            System.out.println("K 的长度小于2了。不太合法的样子。");
            return;
        }
        //数组长度
        int N = arr.length;
        //超过N/K 的数字，可知。有这样的数字是 K-1个
        int [] res = new int[K - 1];
        //定义一个Map的数据结构，key：该位置上出现的数字。 value:出现的次数
        HashMap<Integer,Integer> cands = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if(cands.containsKey(arr[i])){
                //如果map中有了这个key，那么value直接在原来的基础+1就可以了
                cands.put(arr[i],1+cands.get(arr[i]));
            }else {
                //如果map中还没有这个key
                if(cands.size() < K - 1){
                    //如果map中存放的数据长度还没有超过K-1个。则直接放到cands中即可。
                    cands.put(arr[i],1);
                }else {
                    //如果超过了K-1个长度，让所有的map中的value-1即可
                    allCandsMinusOne(cands);
                }
            }
        }
        //获得最后的cands
        HashMap<Integer,Integer> reals = getReals(arr,cands);
        boolean hasPrint = false;
        for (Map.Entry<Integer, Integer> set : cands.entrySet()) {
            //拿到key，作比较，确定是否符合题意超过N/K
            Integer key = set.getKey();
            if(reals.get(key) > N/K){
                hasPrint = true;
                System.out.println("key:"+key);

            }
        }
        System.out.println(hasPrint ? "" : "根本没有这样的数字，耗子为之......");

    }

    private static HashMap<Integer, Integer> getReals(int[] arr, HashMap<Integer, Integer> cands) {
        HashMap<Integer,Integer> reals = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int curNum = arr[i];
            if(cands.containsKey(curNum)){
                reals.put(curNum,reals.get(curNum) + 1);
            }else {
                reals.put(curNum,1);
            }
        }
        return reals;
    }

    private static void allCandsMinusOne(HashMap<Integer, Integer> cands) {
        for (Map.Entry<Integer, Integer> entry : cands.entrySet()) {
            entry.setValue(cands.get(entry)-1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,4,5,2,1,1,1,1,1,1};
        int i = method1(arr);
        System.out.println(i);
        int [] arrMethod2 = {1,2,1,1,5,4,4,1,4};
        int K = 3;
        method2(arrMethod2,K);
    }
}
